Summer Combo in Vermont

Vermont - July 12th 2013

Coxeter-Petrie 1926 - present

Dan Archdeacon, The University of Vermont

Title: Embeddings where all triangles are faces

When embedding a simple graph on a surface one frequently requires that every face is a triangle; this minimalizes the genus of the surface. Here we turn the requirement on its head: "Can we embed a complete multigraph so that every triangle is a face?" I'll present such an embedding for all possible orders.

Karen Collins, Wesleyan University

Title: Nordhaus Gaddum graphs and distinguishing

Let G^c be the complement of graph G. We revisit the Nordhaus-Gaddum inequalities which give bounds on the sum and the product of ?(G) and ?(G^c), the classes of graphs that achieve equality in the bounds, and their distinguishing number analogues.

Jonathon Godbout, University of Vermont

Title: Rook Placements and Colored Permutations

Abstract

Sandra Kingan, Brooklyn College

Title: Strong Splitter Theorem for Graphs and Matroids

Matroids are a modern type of synthetic geometry where the behavior of points, lines, planes and higher dimension surfaces are governed by combinatorial axioms. The Splitter Theorem is a central result in matroid theory since it provides a useful induction tool for structural results. It establishes that (with a few exceptions) if M is a 3-connected matroid with a 3-connected minor N, then we can build-up from N to M by a sequence of single-element extensions and coextensions. However, there is no condition on how many extensions may occur before a coextension must occur. We give a strengthening of the Splitter Theorem, as a result of which, at each step no more than two extensions may occur before a coextension must occur. This sort of stair-stepping approach is the most efficient way of growing a minor to a matroid. This is joint work with Manoel Lemos.

Cory Manack, Amherst College

Title: Ranking Ranked Data via Lattice Path Enumeration

Abstract

Robert McGrail, Bard College

Title: Connectedness and CSP Dichotomy of Finite Quandles

We describe several versions of connectedness in Cayley graphs of finite quandles in order of increasing strength. In particular, we show two seemingly different notions of connectness are the same. This gives rise to a proof of NP/P dichotomy for finite quandles.

Sam Northshield, SUNY-Plattsburgh

Title: a2+b2+c2= (a+b+c)2 and friends

The relatively prime integral solutions a,b,c of the title equation enjoy the surprising property that |a+b|, |a+c|, and |b+c| are all perfect squares. Besides showing this directly, we show how this comes from a parameterization of Ford circles by these solutions. Similarly, relatively prime integral solutions of a2+b2+c2+d2=(a+b+c+d)2 parameterize a one type of "Ford sphere" and solutions of 2(a2+b2+c2+d2)=(a+b+c+d)2, known as "Descartes quadruples", parameterize another.

Lindsay Piechnik, High Point University

Title: Why Nice Triangulations are Nice

Many combinatorial properties of lattice polytopes correspond directly to algebraic properties of toric ideals, and establishing classes of lattice polytopes that admit "nice" coverings and triangulations has implications for algebraic geometry, commutative algebra, and integer programing. My discussion here will focus on one of the nicest relationship, that between
quadratic triangulations and quadratic Grobner bases, and some search methods that have yielded positive results.

John Schmitt, Middlebury College

Title: Approaching the minimum clues Sudoku problem via the polynomial method

Abstract: Determining the minimum number of clues that must be present in a Sudoku puzzle in order for the puzzle to have a unique completion is known as the minimum number of clues problem. It has been conjectured that one needs 17 clues. We apply the polynomial method via a recent result of M. Lason to the analogous 4-by-4 Shidoku board to illustrate how one might approach the more general problem (and problems involving uniquely colorable graphs) with Lason's contribution to the polynomial method.

This is joint work with Aden Forrow.

Brigitte Servatius, Worcester Polytechnic

Title: Coxeter-Petrie 1926 - now

J.F. Petrie was a life long friend of HSM Coxeter. He is a co-author of "the 59 Icosahedra". Coxeter named zig-zag paths after him and we now have Coxeter-Petrie Complexes and the Petrie-dual. We try to survey results and open problems concerning the Petrie-dual.

Christino Tamon, Clarkson University

Title: State Transfer in Quantum Walk on Graphs

Abstract: Given a graph G=(V,E) with adjacency matrix A, a continuous-time quantum walk on G is defined by the matrix
U(t) = exp(-itA) where t is a nonnegative real number. We say that G has perfect state transfer (PST) from vertex a to vertex b at time t if the (a,b)-entry of U(t) has unit magnitude. This notion is motivated by problems in quantum information and computation. In this talk, we survey some basic questions and recent results related to state transfer on graphs.

Peter Winkler, Dartmouth

Title: Should You Be Happy?

Questions involving comparing discrete probabilities can often be phrased by asking whether one should be pleased or not by a particular outcome. We show that such questions can sometimes be answered elegantly by coupling, that is, by a combinatorial merging of different scenarios.